// 跳跃游戏II: https://leetcode-cn.com/problems/jump-game-ii/submissions/

package greedy

// 就是双指针的解法 O(n)的时间复杂度。
// 视频使用 start, end 更好理解，过程也清晰，我自己写的，是这样的。
func jump(nums []int) int {
	n := len(nums)
	cnt := 0
	// 需要二个变量， 一个记录当前位置（idx）， 一个记录当前跳的最远的位置（max）
	idx := 0
	max := 0
	if len(nums) == 1 {
		return 0
	}
	for {
		// 如果当前位置能直接跳到最后，返回跳数加1
		if idx+nums[idx] >= n-1 {
			return cnt + 1
		} else {
			// 上一轮已经比较过了，这轮直接从 上一轮最远处 + 1 位置开始比较
			nextStep := max + 1
			for i := max + 1; i <= idx+nums[idx]; i++ {
				if nums[i]+i > nextStep+nums[nextStep] {
					nextStep = i
				}
			}
			// 跳到能跳的最远的位置， cnt + 1
			max = idx + nums[idx]
			idx = nextStep
			cnt += 1
		}
	}
}

// 双指针解法
func jump(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}
	cnt := 0
	// 初始化跳跃的范围，用双指针表示，start表示当前位置
	// end 表示当前点能跳到的最远位置
	start := 0
	end := start + nums[start]
	// 只要end可以指到最后一个位置，就能到
	for end < n-1 {
		// 找到下一个最优的跳跃点
		for i := start; i <= end; i++ {
			if max(i+nums[i], start+nums[start]) {
				start = i
			}
		}
		// 更新start，end
		// 正常情况下，end 应该更新到 新的start + nums[start] 新的点的最远跳点
		// 只要不是零值，一般来讲 start  应该更新到上一个跳点的 end 位置，因为 新start 到 老 end位置都测试过了,避免重复算
		temp := start
		start = end
		end = temp + nums[temp]
		// 跳一步，加1
		cnt += 1
	}
	return cnt + 1
}

func max(a, b int) bool {
	if a > b {
		return true
	}
	return false
}

// 还是上述思路，最简单的写法！
func jump(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}
	cnt := 0
	maxPos, end := 0, 0
	for i := 0; i < n-1; i++ { // i < n - 1, 注意细节， i < n 这里会出错，有些情况cnt多算1
		// 1. 求出最大跳跃位置
		maxPos = max(maxPos, i+nums[i])
		if i == end {
			// 2. 步数加1
			cnt++
			// 更新end
			end = maxPos
		}
	}
	return cnt
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
